package top150

import (
	"math/rand"
	"sort"
	"strconv"
	"strings"
)

/**
 * @Description 88. Merge Sorted Array
 * @Author kami
 * @Date 2023/8/12 21:29
 **/
func merge(nums1 []int, m int, nums2 []int, n int) {
	if n == 0 {
		return
	}

	if m == 0 {
		for i := 0; i < n; i++ {
			nums1[i] = nums2[i]
		}
	}

	var endIdx = m + n - 1
	var endIdx1 = m - 1
	var endIdx2 = n - 1
	for i := endIdx; i >= 0; i-- {
		if endIdx2 < 0 {
			nums1[i] = nums1[endIdx1]
			endIdx1--
		} else if endIdx1 < 0 {
			nums1[i] = nums2[endIdx2]
			endIdx2--
		} else if nums2[endIdx2] > nums1[endIdx1] {
			nums1[i] = nums2[endIdx2]
			endIdx2--
		} else {
			nums1[i] = nums1[endIdx1]
			endIdx1--
		}
	}

}

/**
 * @Description 27. Remove Element
 * @Author kami
 * @Date 2023/11/1 21:13
 **/
func removeElement(nums []int, val int) int {
	var removeIdx = 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != val {
			nums[removeIdx] = nums[i]
			removeIdx++
		}
	}
	return removeIdx
}

/**
 * @description: 26. Remove Duplicates from Sorted Array
 * @author kami
 * @date 2023/11/2 8:46
 */
func removeDuplicates(nums []int) int {
	var removeIdx = 1
	var curDup = nums[0]
	for i := 0; i < len(nums); i++ {
		if nums[i] != curDup {
			nums[removeIdx] = nums[i]
			removeIdx++
			curDup = nums[i]
		}
	}
	return removeIdx
}

/**
 * @description: 80. Remove Duplicates from Sorted Array II
* @author kami
 * @date 2023/11/2 8:57
*/
func removeDuplicatesII(nums []int) int {
	var curIdx = 0
	for _, num := range nums {
		if curIdx < 2 || num > nums[curIdx-2] {
			nums[curIdx] = num
			curIdx++
		}
	}
	return curIdx
}

/**
 * @description: 169. Majority Element
 * @author kami
 * @date 2023/11/2 9:48
 */
func majorityElement(nums []int) int {
	var val = nums[0]
	var cnt = 1
	for i := 1; i < len(nums); i++ {
		if nums[i] == val {
			cnt++
		} else {
			cnt--
			if cnt == 0 {
				val = nums[i]
				cnt = 1
			}
		}
	}
	return val
}

/**
 * @description: 189. Rotate Array
 * @author kami
 * @date 2023/11/2 9:56
 */
func rotate1(nums []int, k int) {
	var tempNums []int
	for i := 0; i < len(nums); i++ {
		tempNums = append(tempNums, nums[i])
	}
	for i := 0; i < len(tempNums); i++ {
		var nextIdx = (i + k) % len(tempNums)
		nums[nextIdx] = tempNums[i]
	}
}

/**
 * @description: 189. Rotate Array
 * @author kami
 * @date 2023/11/3 9:40
 */
func rotate2(nums []int, k int) {
	reverse(nums, 0, len(nums)-1)
	reverse(nums, 0, k-1)
	reverse(nums, k, len(nums)-1)
}

func reverse(nums []int, start, end int) {
	for start < end && start >= 0 && start < len(nums) && end >= 0 && end < len(nums) {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}
}

func rotate3(nums []int, k int) {
	for k > 0 {
		var temp = nums[len(nums)-1]
		for i := len(nums) - 1; i > 0; i-- {
			nums[i] = nums[i-1]
		}
		nums[0] = temp
		k--
	}
}

/**
 * @description: 121. Best Time to Buy and Sell Stock
 * @author kami
 * @date 2023/11/4 9:46
 */
func maxProfit(prices []int) int {
	var cost = prices[0]
	var profit = 0
	for i := 0; i < len(prices); i++ {
		if prices[i] < cost {
			cost = prices[i]
		}
		if prices[i]-cost > profit {
			profit = prices[i] - cost
		}
	}
	return profit
}

/**
 * @description 122. 买卖股票的最佳时机 II
 * @author kami
 * @date 2023/11/4 12:59
 */
func maxProfitII(prices []int) int {
	var profit = 0
	for i := 1; i < len(prices); i++ {
		var diff = prices[i] - prices[i-1]
		if diff > 0 {
			profit += diff
		}
	}
	return profit
}

/**
 * @description: 55. 跳跃游戏
 * @keyword: 递归，会超时
 * @author: kami
 * @date 2023/11/4 13:07
 */
func canJump(nums []int) bool {
	return canJumpDfs(nums, 0)
}

func canJumpDfs(nums []int, curIdx int) bool {
	var last = len(nums) - 1
	if curIdx == last {
		return true
	}
	if curIdx < last {
		for i := 1; i <= nums[curIdx]; i++ {
			if canJumpDfs(nums, curIdx+i) {
				return true
			}
		}
	}
	return false
}

/**
 * @description: 55. 跳跃游戏
 * @keyword: 动态规划
 * @author: kami
 * @date 2023/11/4 13:37
 */
func canJump2(nums []int) bool {
	var jumpNums = make([]int, len(nums))
	return canJumpDfs2(nums, jumpNums, 0)
}
func canJumpDfs2(nums []int, jumpNums []int, curIdx int) bool {
	if curIdx == len(nums)-1 || jumpNums[curIdx] == 1 {
		return true
	}
	if curIdx >= len(nums) || jumpNums[curIdx] == -1 {
		return false
	}

	for i := 1; i <= nums[curIdx]; i++ {
		if canJumpDfs2(nums, jumpNums, curIdx+i) {
			jumpNums[curIdx] = 1
			return true
		}
	}
	jumpNums[curIdx] = -1

	return false
}

/*
*
  - @description: 55. 跳跃游戏
  - @keyword: 跳到最远

如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
如果可以一直跳到最后，就成功了
  - @author: kami
  - @date 2023/11/4 14:22
*/
func canJump3(nums []int) bool {
	var k = 0
	for i := 0; i < len(nums); i++ {
		if i > k {
			return false
		}
		if i+nums[i] > k {
			k = i + nums[i]
		}
	}
	return true
}

/**
 * @description: 45. 跳跃游戏 II
 * @keyword: 顺藤摸瓜
 * @author: kami
 * @date 2023/11/4 14:35
 */
func jump(nums []int) int {
	var end, maxPosition, steps int
	for i := 0; i < len(nums)-1; i++ {
		if nums[i]+i > maxPosition {
			maxPosition = nums[i] + i
		}
		if i == end {
			end = maxPosition
			steps++
		}
	}
	return steps
}

/**
 * @description: 274. H 指数
* @keyword:
 * @author: kami
 * @date 2023/11/5 15:23
*/
func hIndex(citations []int) int {
	sort.Ints(citations)
	var h int
	for i := len(citations) - 1; i >= 0 && citations[i] > h; i-- {
		h++
	}
	return h
}

func hIndex1(citations []int) int {
	n := len(citations)
	counter := make([]int, n+1)
	for _, citation := range citations {
		if citation >= n {
			counter[n]++
		} else {
			counter[citation]++
		}
	}
	for i, tot := n, 0; i >= 0; i-- {
		tot += counter[i]
		if tot >= i {
			return i
		}
	}
	return 0
}

/**
 * @description: 380. O(1) 时间插入、删除和获取随机元素
* @keyword:
 * @author: kami
 * @date 2023/11/5 17:49
*/
type RandomizedSet struct {
	nums []int
	set  map[int]int
}

func Constructor() RandomizedSet {
	return RandomizedSet{
		set: make(map[int]int),
	}
}

func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.set[val]; ok {
		return false
	}
	this.nums = append(this.nums, val)
	this.set[val] = len(this.nums) - 1
	return true
}

func (this *RandomizedSet) Remove(val int) bool {
	if idx, ok := this.set[val]; ok {
		var last = len(this.nums) - 1
		this.nums[idx] = this.nums[last]
		this.set[this.nums[idx]] = idx
		this.nums = this.nums[:last]
		delete(this.set, val)
		return true
	}
	return false
}

func (this *RandomizedSet) GetRandom() int {
	return this.nums[rand.Intn(len(this.nums))]
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */
/**
 * @description: 238. 除自身以外数组的乘积
 * @keyword: 前后乘机
 * @author: kami
 * @date 2023/11/7 8:38
 */
func productExceptSelf(nums []int) []int {
	var res = make([]int, len(nums))
	res[len(nums)-1] = nums[len(nums)-1]
	for i := len(nums) - 2; i >= 0; i-- {
		res[i] = res[i+1] * nums[i]
	}
	res[0] = res[1]
	var preProduct = nums[0]
	for i := 1; i < len(nums)-1; i++ {
		res[i] = res[i+1] * preProduct
		preProduct *= nums[i]
	}
	res[len(nums)-1] = preProduct
	return res
}

/**
 * @description: 134. 加油站
 * @keyword:
 * @author: kami
 * @date 2023/11/7 9:44
 */
func canCompleteCircuit(gas []int, cost []int) int {
	var leftGas = make([]int, len(gas))
	var sumLeftGas = 0
	for i := 0; i < len(gas); i++ {
		leftGas[i] = gas[i] - cost[i]
		sumLeftGas += leftGas[i]
	}
	if sumLeftGas < 0 {
		return -1
	}
	var start int
	var allGasLeft int
	for i := 0; i < len(leftGas); i++ {
		allGasLeft += leftGas[i]
		if allGasLeft < 0 {
			allGasLeft = 0
			start = i + 1
		}
	}
	return start
}

/**
 * @Description 135. 分发糖果
 * @Author kami
 * @Date 2023/11/7 18:02
 **/
func candy(ratings []int) (ans int) {
	n := len(ratings)
	left := make([]int, n)
	for i, r := range ratings {
		if i > 0 && r > ratings[i-1] {
			left[i] = left[i-1] + 1
		} else {
			left[i] = 1
		}
	}
	right := 0
	for i := n - 1; i >= 0; i-- {
		if i < n-1 && ratings[i] > ratings[i+1] {
			right++
		} else {
			right = 1
		}
		ans += max(left[i], right)
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

/**
 * @description: 42. 接雨水
 * @keyword:
 * @author: kami
 * @date 2023/11/8 9:01
 */
func trap(height []int) int {
	var n = len(height)
	// left[i]表示i左边的最大值，right[i]表示i右边的最大值
	var left = make([]int, n)
	var right = make([]int, n)
	for i := 1; i < n; i++ {
		left[i] = max(left[i-1], height[i-1])
	}
	for i := n - 2; i >= 0; i-- {
		right[i] = max(right[i+1], height[i+1])
	}
	var water int
	for i := 0; i < n; i++ {
		var level = min(left[i], right[i])
		water += max(0, level-height[i])
	}
	return water
}

/*
*
  - @Description 13. 罗马数字转整数

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
  - @Author kami
  - @Date 2023/11/8 16:13
    *
*/
func romanToInt(s string) int {
	var res int
	var i int
	for i < len(s) {
		if i+1 < len(s) {
			if s[i] == 'I' && s[i+1] == 'V' {
				res += 4
			} else if s[i] == 'I' && s[i+1] == 'X' {
				res += 9
			} else if s[i] == 'X' && s[i+1] == 'L' {
				res += 9
			} else if s[i] == 'I' && s[i+1] == 'X' {
				res += 9
			} else if s[i] == 'I' && s[i+1] == 'X' {
				res += 9
			} else if s[i] == 'I' && s[i+1] == 'X' {
				res += 9
			}
		}
	}
	return 0
}

/**
 * @description: 58. 最后一个单词的长度
 * @keyword:
 * @author: kami
 * @date 2023/11/9 9:22
 */
func lengthOfLastWord(s string) int {
	s = strings.TrimSpace(s)
	var cnt int
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == ' ' {
			return cnt
		}
		cnt++
	}
	return cnt
}

/**
 * @description: 14. 最长公共前缀
 * @keyword:
 * @author: kami
 * @date 2023/11/9 9:26
 */
func longestCommonPrefix(strs []string) string {
	var minLength = len(strs[0])
	for i := 0; i < len(strs); i++ {
		if len(strs[i]) < minLength {
			minLength = len(strs[i])
		}
		if len(strs[i]) == 0 {
			return ""
		}
	}
	for i := 1; i < len(strs); i++ {
		for j := 0; j < minLength; j++ {
			if strs[i][j] != strs[i-1][j] {
				minLength = j
				break
			}
		}
		if minLength <= 0 {
			return ""
		}
	}
	return strs[0][0:minLength]
}

/*
*
  - @description: 13. 罗马数字转整数
  - @keyword: 通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。

例如 XXVII\texttt{XXVII}XXVII 可视作 X+X+V+I+I=10+10+5+1+1=27\texttt{X}+\texttt{X}+\texttt{V}+\texttt{I}+\texttt{I}=10+10+5+1+1=27X+X+V+I+I=10+10+5+1+1=27。
若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。
  - @author: kami
  - @date 2023/11/13 8:56
*/
var symbolValues = map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

func romanToInt1(s string) (ans int) {
	n := len(s)
	for i := range s {
		value := symbolValues[s[i]]
		if i < n-1 && value < symbolValues[s[i+1]] {
			ans -= value
		} else {
			ans += value
		}
	}
	return
}

/**
 * @description: 12. 整数转罗马数字
 * @keyword:
 * @author: kami
 * @date 2023/11/13 21:22
 */
var (
	thousands = []string{"", "M", "MM", "MMM"}
	hundreds  = []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
	tens      = []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
	ones      = []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
)

func intToRoman(num int) string {
	return thousands[num/1000] + hundreds[num%1000/100] + tens[num%100/10] + ones[num%10]
}

/**
 * @description: 151. 反转字符串中的单词
 * @keyword:
 * @author: kami
 * @date 2023/11/13 9:00
 */
func reverseWords(s string) string {
	t := strings.Fields(s)          //使用该函数可切割单个/多个空格，提取出单词
	for i := 0; i < len(t)/2; i++ { //遍历数组的前半段直接交换即可
		t[i], t[len(t)-1-i] = t[len(t)-1-i], t[i]
	}
	res := strings.Join(t, " ") //重新使用空格连接多个单词
	return res
}

/**
 * @description: 6. N 字形变换
 * @keyword:
 * @author: kami
 * @date 2023/11/13 21:33
 */
func convert(s string, numRows int) string {
	if numRows < 2 {
		return s
	}
	var numsArray = make([][]int32, numRows)
	var i = 0
	var down = -1
	for _, c := range s {
		numsArray[i] = append(numsArray[i], c)
		if i == 0 || i == numRows-1 {
			down = -down
		}
		i += down
	}
	var res string
	for i := 0; i < numRows; i++ {
		res += string(numsArray[i])
	}
	return res
}

/**
 * @description: 28. 找出字符串中第一个匹配项的下标
 * @keyword:
 * @author: kami
 * @date 2023/11/13 22:26
 */
func strStr(haystack string, needle string) int {
	nlen := len(needle)
	hlen := len(haystack)
	if hlen < nlen {
		return -1
	}
	// 窗口滑动法，每次在 haystack 上切割 needle 长度的字符串，看看是否与 needle 相等
	for i := nlen; i <= hlen; i++ {
		if haystack[i-nlen:i] == needle {
			return i - nlen
		}
	}
	return -1
}

/**
 * @description: 125. 验证回文串
 * @keyword:
 * @author: kami
 * @date 2023/11/14 9:23
 */
func isPalindrome(s string) bool {
	s = strings.ToLower(s)
	left, right := 0, len(s)-1
	for left < right {
		for left < right && !isLetterNum(s[left]) {
			left++
		}
		for left < right && !isLetterNum(s[right]) {
			right--
		}
		if left < right {
			if s[left] != s[right] {
				return false
			}
			left++
			right--
		}
	}
	return true
}
func isLetterNum(a byte) bool {
	return (a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z') || (a >= '0' && a <= '9')
}
func equal(a, b byte) bool {
	return a == b || a-'a' == b-'A' || a-'A' == b-'a'
}

/**
 * @Description 392. 判断子序列
 * @Author kami
 * @Date 2023/11/15 16:43
 **/
func isSubsequence(s string, t string) bool {
	var tIdx = 0
	for i := 0; i < len(s); i++ {
		var find = false
		for tIdx < len(t) {
			if s[i] == t[tIdx] {
				find = true
				tIdx++
				break
			}
			tIdx++
		}
		if !find {
			return false
		}
	}
	return true
}

/**
 * @Description 167. 两数之和 II - 输入有序数组
 * @Author kami
 * @Date 2023/11/15 16:52
 **/
func twoSum(numbers []int, target int) []int {
	var left = 0
	var right = len(numbers) - 1
	for left < right {
		sum := numbers[left] + numbers[right]
		if sum == target {
			return []int{left + 1, right + 1}
		} else if sum < target {
			left++
		} else {
			right--
		}
	}
	return []int{left, right}
}

func maxArea(height []int) int {
	var left = 0
	var right = len(height) - 1
	var max = 0
	for left < right {
		var wide = right - left
		var minHeight = height[left]
		if height[right] < minHeight {
			minHeight = height[right]
			right--
		} else {
			left++
		}

		var water = wide * minHeight
		if water > max {
			max = water
		}

	}
	return max
}

/**
 * @description: 15. 三数之和
 * @keyword: 排序，两数之和
 * @author: kami
 * @date 2023/11/15 20:52
 */
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var res [][]int
	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 {
			break
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		var left = i + 1
		var right = len(nums) - 1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == 0 {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				for left < right && nums[left] == nums[left+1] {
					left++
				}
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				left++
				right--
			} else if sum > 0 {
				right--
			} else {
				left++
			}
		}
	}
	return res
}

/**
 * @description: 209. 长度最小的子数组
 * @keyword:
 * @author: kami
 * @date 2023/11/15 21:10
 */
func minSubArrayLen(target int, nums []int) int {
	i := 0
	l := len(nums)  // 数组长度
	sum := 0        // 子数组之和
	result := l + 1 // 初始化返回长度为l+1，目的是为了判断“不存在符合条件的子数组，返回0”的情况
	for j := 0; j < l; j++ {
		sum += nums[j]
		for sum >= target {
			subLength := j - i + 1
			if subLength < result {
				result = subLength
			}
			sum -= nums[i]
			i++
		}
	}
	if result == l+1 {
		return 0
	} else {
		return result
	}
}

/**
 * @description: 383. 赎金信
* @keyword: 数组下标代表字母
 * @author: kami
 * @date 2023/11/19 11:27
*/
func canConstruct(ransomNote string, magazine string) bool {
	var magazineMeetTimes = make([]int, 26)
	for i := 0; i < len(magazine); i++ {
		magazineMeetTimes[magazine[i]-'a']++
	}
	for i := 0; i < len(ransomNote); i++ {
		if magazineMeetTimes[ransomNote[i]-'a'] == 0 {
			return false
		}
		magazineMeetTimes[ransomNote[i]-'a']--
	}
	return true
}

/*
*
  - @description: 205. 同构字符串
  - @keyword: 开启循环同时扫描s 和 t，用两个map建立 s 字符和 t 字符的双向映射
    如果两个都是没有遇过的字符，就同时存入map，形成双向映射
    如果两个是之前遇过的字符，就看当前的字符和map中的映射值匹不匹配
    如果匹配，就继续扫下一个字符
    如果不匹配，说明不同构，比如egg和ada，g应该映射d，但现在遇到a(虽然a遇到过)
    如果其中一个是之前遇到过，另一个之前没遇过，就直接返回false
    比如 egg 和 adc，g 是之前遇到的，c是没遇到的(c理应为d，理应遇到过)
    如果循环结束始终没有返回false，则返回true。
  - @author: kami
  - @date 2023/11/19 11:30
*/
func isIsomorphic(s string, t string) bool {
	s2t := map[byte]byte{}
	t2s := map[byte]byte{}

	for i := 0; i < len(s); i++ {
		a1, ok1 := s2t[s[i]]
		a2, ok2 := t2s[t[i]]

		if ok1 && ok2 {
			if a1 != t[i] || a2 != s[i] {
				return false
			}
		} else if !ok1 && !ok2 {
			s2t[s[i]] = t[i]
			t2s[t[i]] = s[i]
		} else {
			return false
		}
	}
	return true
}

/**
 * @description: 228. 汇总区间
 * @keyword:
 * @author: kami
 * @date 2023/11/19 11:52
 */
func summaryRanges(nums []int) []string {
	var ans []string
	for i, n := 0, len(nums); i < n; {
		left := i
		for i++; i < n && nums[i-1]+1 == nums[i]; i++ {
		}
		s := strconv.Itoa(nums[left])
		if left < i-1 {
			s += "->" + strconv.Itoa(nums[i-1])
		}
		ans = append(ans, s)
	}
	return ans
}

/**
 * @description:
 * @keyword:
 * @author: kami
 * @date 2023/11/20 9:52
 */
func wordPattern(pattern string, s string) bool {
	word2ch := map[string]byte{}
	ch2word := map[byte]string{}
	words := strings.Split(s, " ")
	if len(pattern) != len(words) {
		return false
	}
	for i, word := range words {
		ch := pattern[i]
		if word2ch[word] > 0 && word2ch[word] != ch || ch2word[ch] != "" && ch2word[ch] != word {
			return false
		}
		word2ch[word] = ch
		ch2word[ch] = word
	}
	return true
}

func containsNearbyDuplicate(nums []int, k int) bool {
	var numsMap = make(map[int][]int)
	for i := 0; i < len(nums); i++ {
		if idxList, ok := numsMap[nums[i]]; ok {
			for x := 0; x <= len(idxList); x++ {
				if nums[i] == nums[x] && i-x <= k && i-x >= -k {
					return true
				}
			}
			idxList = append(idxList, i)
		} else {
			numsMap[nums[i]] = []int{i}
		}
	}
	return false
}

type Node struct {
	Val   int
	Left  *Node
	Right *Node
	Next  *Node
}

func connect(root *Node) *Node {
	if root == nil {
		return nil
	}
	var list = []*Node{root}
	for len(list) > 0 {
		var newList []*Node
		for i := 0; i < len(list); i++ {
			if list[i].Left != nil {
				newList = append(newList, list[i].Left)
			}
			if list[i].Right != nil {
				newList = append(newList, list[i].Right)
			}
			if i < len(list)-1 {
				list[i].Next = list[i+1]
			}
		}
		list = newList
	}
	return root
}
